#include <iostream>
#include <vector>
#include <iterator>
#include <fstream>

using namespace std;

// read cases from the file
vector< vector<int> > buildCases(ifstream& file)
{
	vector< vector<int> > nCases;
	char strLine[1024] = {0};
	int nColumn = 0;
	int nRow = 0;
	while (file.getline(strLine, sizeof(strLine)))
	{
		vector<int> nLine;
		for (unsigned int i = 0; i < strlen(strLine); ++i)
		{
			if (strLine[i] != ' ')
			{
				nLine.push_back(strLine[i] - '0');
			}
		}
		nCases.push_back(nLine);
	}
	return nCases;
}

// generate requires
vector<int> buidRequires(const unsigned int& size)
{
	vector<int> nRequires;
	for (unsigned int i = 0; i < size; ++i)
		nRequires.push_back(1);
	return nRequires;
}

// whether the requires is empty
bool isRequiresEmpty(const vector<int>& requires)
{
	bool bEmpty = true;
	for (unsigned int i = 0; i < requires.size(); ++i)
	{
		if (requires[i] != 0)
		{
			bEmpty = false;
			break;
		}
	}
	return bEmpty;
}

// find the case who can achieve most requires
int findBestCase(const vector<int>& requires, const vector< vector<int> >& cases)
{
	int nBestCaseIndex = -1;
	int nMaxAchieveCount = 0;
	for (unsigned int i = 0; i < cases.size(); ++i)
	{
		int nAchieveCount = 0;
		for (unsigned int j = 0; j < cases[i].size(); ++j)
			if (requires[j] == 1 && cases[i][j] == 1)
				++nAchieveCount;
		if (nAchieveCount > nMaxAchieveCount)
		{
			nMaxAchieveCount = nAchieveCount;
			nBestCaseIndex = i;
		}
	}
	return nBestCaseIndex;
}

// delete the best case and the requires it achieved
void deleteBestCaseAndRequires(vector<int>& bestcase, vector<int>& requires)
{
	for (unsigned int i = 0; i < bestcase.size(); ++i)
	{
		if (bestcase[i] == 1)
		{
			bestcase[i] = 0;
			requires[i] = 0;
		}
	}
}

// find a necessary case who can achieve the requires
int findNecessaryCase(const vector<int>& requires, const vector< vector<int> >& cases)
{
	int nNecessaryCaseIndex = -1;
	for (unsigned int i = 0; i < requires.size(); ++i)
	{
		if (requires[i] != 1)
			continue;
		int nCaseIndex = 0;
		int nCaseCount = 0;
		for (unsigned int j = 0; j < cases.size(); ++j)
		{
			if (cases[j][i] == 1)
			{
				nCaseIndex = j;
				++nCaseCount;
			}
		}
		if (nCaseCount == 1)
		{
			nNecessaryCaseIndex = nCaseIndex;
			break;
		}
	}
	return nNecessaryCaseIndex;
}

// delete the requires the necessary case achieved
void deleteRequiresInNecessaryCase(vector<int>& requires, const vector<int>& necessarycase)
{
	for (unsigned int i = 0; i < necessarycase.size(); ++i)
	{
		if (necessarycase[i] == 1)
			requires[i] = 0;
	}
}

// delete redundant cases
void deleteRedundantCases(vector< vector<int> >& cases, const int& index)
{
	for (unsigned int i = 0; i < cases.size(); ++i)
	{
		if (i == index)
			continue;
		bool bRedundant = true;
		for (unsigned int j = 0; j < cases[index].size(); ++j)
		{
			if (cases[i][j] == 1 && cases[index][j] == 0)
			{
				bRedundant = false;
				break;
			}
		}
		if (bRedundant)
		{
			for (unsigned int j = 0; j < cases[i].size(); ++j)
				cases[i][j] = 0;
		}
	}
}

// calculate the number of the cases who can achieve the require
int calculateCaseCount(const int& requireindex, const vector< vector<int> >& cases)
{
	int nCasesCount = 0;
	for (unsigned int i = 0; i < cases.size(); ++i)
	{
		if (cases[i][requireindex] == 1)
			++nCasesCount;
	}
	return nCasesCount;
}

// sort requires by the number of the cases who can achieve each require
vector< vector<int> > divideRequires(const vector<int>& requires, const vector< vector<int> >& cases)
{
	vector< vector<int> > nDividedRequires;
	for (unsigned int i = 0; i <= cases.size(); ++i)
	{
		vector<int> nCaseCountIRequires;
		for (unsigned j = 0; j < requires.size(); ++j)
		{
			if (calculateCaseCount(j, cases) == i)
				nCaseCountIRequires.push_back(j);
		}
		nDividedRequires.push_back(nCaseCountIRequires);
	}
	return nDividedRequires;
}

// find the first case who can achieve the require
int findFirstCase(const int& requireindex, const vector< vector<int> >& cases)
{
	int nCaseIndex = -1;
	for (unsigned int i = 0; i < cases.size(); ++i)
	{
		if (cases[i][requireindex] == 1)
		{
			nCaseIndex = i;
			break;
		}
	}
	return nCaseIndex;
}

// delete the requires the case achieved
void deleteRequiresInCase(vector<int>& requires, const vector<int>& thecase)
{
	for (unsigned int i = 0; i < thecase.size(); ++i)
	{
		if (thecase[i] == 1)
			requires[i] = 0;
	}
}

// greedy algorithm
vector<int> greedyAlgorithm(vector< vector<int> > cases, vector<int> requires)
{
	vector<int> nCaseIndexes;
	while (!isRequiresEmpty(requires) && cases.size() > 0)
	{
		int nBestCaseIndex = findBestCase(requires, cases);
		if (nBestCaseIndex == -1)
			break;
		nCaseIndexes.push_back(nBestCaseIndex);
		deleteBestCaseAndRequires(cases[nBestCaseIndex], requires);
	}
	return nCaseIndexes;
}

// GRE algorithm
vector<int> greAlgorithm(vector< vector<int> > cases, vector<int> requires)
{
	vector<int> nCaseIndexes;
	int nNecessaryCaseIndex = -1;
	while ((nNecessaryCaseIndex = findNecessaryCase(requires, cases)) != -1)
	{
		nCaseIndexes.push_back(nNecessaryCaseIndex);
		deleteRequiresInNecessaryCase(requires, cases[nNecessaryCaseIndex]);
		deleteRedundantCases(cases, nNecessaryCaseIndex);
	}
	if (!isRequiresEmpty(requires))
	{
		vector<int> nIndexesByGreedy = greedyAlgorithm(cases, requires);
		copy(nIndexesByGreedy.begin(), nIndexesByGreedy.end(), back_inserter(nCaseIndexes));
	}
	return nCaseIndexes;
}

// H algorithm
vector<int> hAlgorithm(vector< vector<int> > cases, vector<int> requires)
{
	vector<int> nCaseIndexes;
	vector< vector<int> > nDividedRequires = divideRequires(requires, cases);
	for (unsigned int i = 1; i <= cases.size(); ++i)
	{
		for (unsigned int j = 0; j < nDividedRequires[i].size(); ++j)
		{
			if (requires[nDividedRequires[i][j]] == 0)
				continue;
			int nRequireIndex = nDividedRequires[i][j];
			int nCaseIndex = findFirstCase(nRequireIndex, cases);
			nCaseIndexes.push_back(nCaseIndex);
			deleteRequiresInCase(requires, cases[nCaseIndex]);
		}
	}
	return nCaseIndexes;
}

// print case indexes
void printCaseIndexes(const vector<int>& cases)
{
	for (unsigned int i = 0; i < cases.size(); ++i)
		cout << "t" << cases[i] + 1 << ", ";
	cout << endl;
}

int main(int argc, char** argv)
{
	ifstream infile("input.txt", ios::in);
	if (!infile)
	{
		cout << "Input file not exist." << endl;
		goto Exit0;
	}

	{
		vector< vector<int> > nCases = buildCases(infile);
		vector<int> nRequires = buidRequires(nCases[0].size());

		vector<int> nCasesByGreedy = greedyAlgorithm(nCases, nRequires);
		cout << "Cases by greedy algorithm are: ";
		printCaseIndexes(nCasesByGreedy);

		vector<int> nCasesByGRE = greAlgorithm(nCases, nRequires);
		cout << "Cases by GRE algorithm are: ";
		printCaseIndexes(nCasesByGRE);

		vector<int> nCasesByH = hAlgorithm(nCases, nRequires);
		cout << "Cases by H algorithm are: ";
		printCaseIndexes(nCasesByH);
	}

Exit0:
	cout << "Press the <Enter> key to exit.";
	getchar();
}